package com.algorithm.ch1.lzr.array;

/**
 * 将数组中的0移动到最后  存在多个0如何操作
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * <p>
 * 必须在原数组上操作, 不能拷贝额外的数组
 * 尽量减少操作次数
 *
 * @author lzr
 * @date 2018/8/7
 */
public class MoveZeroes {
    public static void main(String[] args) {
        int[] array1 = {0, 1, 0, 3, 12};
        moveZeroes1(array1);
        for (int i = 0; i < array1.length; i++) {
            System.out.println(array1[i]);
        }
        int[] array2 = {0, 1, 0, 3, 12, 0, 39, 2, 3};
        moveZeroes2(array2);
        for (int i = 0; i < array2.length; i++) {
            System.out.println(array2[i]);
        }
    }

    /**
     * 从array[i]不等于0 的方向去处理
     * 用count记录0的次数
     *
     * @param array
     */
    public static void moveZeroes1(int[] array) {
        if (null == array || array.length < 2) {
            return;
        }
        //记录为0的次数
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            //array[i]=0才处理
            if (array[i] == 0) {
                count++;
            } else {
                //将非0的数据往前挪
                array[i - count] = array[i];
            }
        }
        //将最后的数据置0
        for (int i = 1; i <= count; i++) {
            array[array.length - i] = 0;
        }
    }

    /**
     * 从array[i]不等于0 的方向去处理
     * 用index从0开始计数, 用array[index]存非0数据
     *
     * @param array
     */
    public static void moveZeroes2(int[] array) {
        if (null == array || array.length < 2) {
            return;
        }
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] != 0) {
                array[index++] = array[i];
            }
        }
        for (int i = index; i < array.length; i++) {
            array[i] = 0;
        }
    }

}
